#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <deque>

using namespace std;

class Solution {
private:
    void dfs(unordered_map<string, deque<string>>& routes, string src, vector<string>& order) {
        deque<string>& route = routes[src];
        while (route.size() > 0) {
            string front = route.front();
            route.pop_front();
            dfs(routes, front, order);
        }
        order.push_back(src);
    }
public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        unordered_map<string, deque<string>> routes;
        for (vector<vector<string>>::iterator it = tickets.begin(); it != tickets.end(); it++) {
            routes[(*it)[0]].push_back((*it)[1]);
        }
        for (unordered_map<string, deque<string>>::iterator it = routes.begin(); it != routes.end(); it++) {
            deque<string>& dist = it->second;
            sort(dist.begin(), dist.end());
        }
        vector<string> order;
        dfs(routes, "JFK", order);
        reverse(order.begin(), order.end());
        return order;
    }
};

int main() {
    vector<vector<string>> input = {{"JFK", "KUL"}, {"JFK", "NRT"}, {"NRT", "JFK"}};
    Solution solution;
    vector<string> output = solution.findItinerary(input);
    for (string item : output) {
        cout << item << " ";
    }
    cout << endl;
    return 0;
}